package com.zwj.interview.两数和;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * @Author: Zwj
 * @Date: 2022/2/28 17:45
 * <p>
 * 输入一个数组，请输出等于目标值target的元素对，元素对不能重复
 * 比如：[1,3,1,2,2,3]  target=4
 * 输出：[[1,3],[2,2]]  因为（1,3）和（3,1）是相同的元素对
 */
public class 两数和3 {

    public List<List<Integer>> twoSum(int[] nums, int target) {
        //先给元素排序
        Arrays.sort(nums);
        List<List<Integer>> res = new ArrayList<>();
        int lo = 0, hi = nums.length - 1;
        //记录索引lo和hi最初对应的元素值
        while (lo < hi) {
            int left = nums[lo];
            int right = nums[hi];
            int sum = nums[lo] + nums[hi];
            if (sum < target) {
                lo++;
            } else if (sum > target) {
                hi--;
            } else {
                //找到两个目标值了
                res.add(Arrays.asList(left, right));
                //需要跳过相同的元素
                while (nums[lo] == left) {
                    lo++;
                }
                while (nums[hi] == right) {
                    hi--;
                }
            }
        }
        return res;
    }


    //还是利用二分法思想
    public List<List<Integer>> twoSum2(int[] nums, int target) {
        //这一步是关键
        Arrays.sort(nums);
        List<List<Integer>> res=new ArrayList<>();
        int lo=0;
        int high=nums.length-1;
        while(lo<high){
            int left=nums[lo];
            int right=nums[high];
            int sum=nums[lo]+nums[high];
            if(sum<target){
                lo++;
            }else if(sum>target){
                high--;
            }else{
                //两个数等于目标值了
                res.add(Arrays.asList(left,right));
                while(nums[lo]==left){
                    lo++;
                }
                while(nums[high]==right){
                    high--;
                }
            }
        }
        return res;
    }



    public static void main(String[] args) {
        System.out.println(new 两数和3().twoSum2(new int[]{1,3,1,2,2,3},4));
    }
}